/*
 * Created on 15 avr. 2005 by Tudor.Ionescu@supelec.fr
 */
package clustering.framework;

import java.util.*;

/**
 * @author Tudor.Ionescu@supelec.fr
 * @
 */
public class Quartet{
    public int [] nodes = new int[4];
    public double weight = 0;
    public int K = Integer.MAX_VALUE;
    public int d = -1;
    public int cni = -1;
    public int pni1 = -1;
    public int pni2 = -1;
    public boolean consistent = false;
    public static Double best_cost;
    public static Double worst_cost;
    public Quartet(int a, int b, int c, int d,double [][] dMatrix){
        nodes[0] = a;
        nodes[1] = b;
        nodes[2] = c;
        nodes[3] = d;
        this.weight = dMatrix[a][b] + dMatrix[c][d];// - (1.0 / 2.0)* (dMatrix[a][c]+dMatrix[a][d]+dMatrix[c][b]+dMatrix[d][b]);
    }
    public static ArrayList generateDiffQuartetList(double [][] dm){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                if(i != dm.length - 1 && j != dm.length - 1 && k != dm.length - 1 && l != dm.length - 1){
                    continue;
                }else{
	                Quartet q1 = new Quartet(i,j,k,l,dm);
	                alQuartets.add(q1);
	                Quartet q2 = new Quartet(i,k,j,l,dm);
	                alQuartets.add(q2);
	                Quartet q3 = new Quartet(i,l,j,k,dm);
	                alQuartets.add(q3);
                }
              }
            }
          }
        }
        return alQuartets;
    }
    public static ArrayList generateDiff2QuartetList(double [][] dm){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                if(i != dm.length - 1 && j != dm.length - 1 && k != dm.length - 1 && l != dm.length - 1){
                    continue;
                }else if(i != dm.length - 2 && j != dm.length - 2 && k != dm.length - 2 && l != dm.length - 2){
            		continue;
            	}else{                	
	                Quartet q1 = new Quartet(i,j,k,l,dm);
	                alQuartets.add(q1);
	                /*
	                Quartet q2 = new Quartet(i,k,j,l,dm);
	                alQuartets.add(q2);
	                Quartet q3 = new Quartet(i,l,j,k,dm);
	                alQuartets.add(q3);
	                */
                }
              }
            }
          }
        }
        return alQuartets;
    }
    
    public static int [] quartetCount = null;
    public static Quartet [] generateDiff2QuartetListReduced(double [][] dm, int del_k){
    	if(quartetCount == null)quartetCount = new int[dm.length+1];
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                if(i != dm.length - 1 && j != dm.length - 1 && k != dm.length - 1 && l != dm.length - 1){
                    continue;
                }else if(i != dm.length - 2 && j != dm.length - 2 && k != dm.length - 2 && l != dm.length - 2){
            		continue;
            	}else{                	
	                Quartet q1 = new Quartet(i,j,k,l,dm);
	                alQuartets.add(q1);
	                /*
	                Quartet q2 = new Quartet(i,k,j,l,dm);
	                alQuartets.add(q2);
	                Quartet q3 = new Quartet(i,l,j,k,dm);
	                alQuartets.add(q3);
	                */
                }
              }
            }
          }
        }
        for(int i=quartetCount.length-1;i>=1;i--)
        {
        	quartetCount[i] = quartetCount[i-1];
        }
        quartetCount[0] = alQuartets.size();
        
        int old_index = -1;
        Random rand = new Random();
        for(int i=0;i<del_k;i++)
        {
        	int new_index = rand.nextInt(alQuartets.size());
        	while(new_index == old_index)
        	{
        		new_index = rand.nextInt(alQuartets.size());
        	}
        	alQuartets.remove(new_index);
        	old_index = new_index;
        }
        Quartet [] quartets = new Quartet[alQuartets.size()];
        for(int i=0;i<quartets.length;i++)
        {
        	quartets[i] = (Quartet)alQuartets.get(i);
        }
        return quartets;
    }
    public static Quartet [] generateDiff2QuartetList2(double [][] dm){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                if(i != dm.length - 1 && j != dm.length - 1 && k != dm.length - 1 && l != dm.length - 1){
                    continue;
                }else if(i != dm.length - 2 && j != dm.length - 2 && k != dm.length - 2 && l != dm.length - 2){
            		continue;
            	}else{                	
	                Quartet q1 = new Quartet(i,j,k,l,dm);
	                alQuartets.add(q1);
	                /*
	                Quartet q2 = new Quartet(i,k,j,l,dm);
	                alQuartets.add(q2);
	                Quartet q3 = new Quartet(i,l,j,k,dm);
	                alQuartets.add(q3);
	                */
                }
              }
            }
          }
        }
        Quartet [] quartets = new Quartet[alQuartets.size()];
        for(int i=0;i<quartets.length;i++)
        {
        	quartets[i] = (Quartet)alQuartets.get(i);
        }
        return quartets;
    }
    public static ArrayList generateBestDiffQuartetList(double [][] dm){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                if(i != dm.length - 1 && j != dm.length - 1 && k != dm.length - 1 && l != dm.length - 1){
                    continue;
                }else{
                	Quartet q1 = new Quartet(i,j,k,l,dm);
                    //alQuartets.add(q1);
                    Quartet q2 = new Quartet(i,k,j,l,dm);
                    //alQuartets.add(q2);
                    Quartet q3 = new Quartet(i,l,j,k,dm);
                    //alQuartets.add(q3);
                    if(q1.weight < q2.weight && q1.weight < q3.weight){
                    	alQuartets.add(q1);
                    }else if(q2.weight < q1.weight && q2.weight < q3.weight){
                    	alQuartets.add(q2);
                    }else{
                    	alQuartets.add(q3);
                    }
                }
              }
            }
          }
        }
        return alQuartets;
    }
    
//  generates the full (n 4)T combinations quartets list 
    public static ArrayList generateFullQuartetList(double [][] dm){
        double wmin, wmax, best, worst;
        ArrayList alQuartets = new ArrayList();
        worst = best = 0.0;
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                Quartet q1 = new Quartet(i,j,k,l,dm);
                alQuartets.add(q1);
                /*
                Quartet q2 = new Quartet(i,k,j,l,dm);
                alQuartets.add(q2);
                Quartet q3 = new Quartet(i,l,j,k,dm);
                alQuartets.add(q3);
                wmin = min(q1.weight,q2.weight,q3.weight);
                wmax = max(q1.weight,q2.weight,q3.weight);
                worst += wmax;
                best += wmin;
                */
              }
            }
          }
        }
        //worst_cost = new Double(worst);
        //best_cost = new Double(best);
        return alQuartets;
    }
    public static ArrayList generate3FullQuartetList(double [][] dm){
        double wmin, wmax, best, worst;
        ArrayList alQuartets = new ArrayList();
        worst = best = 0.0;
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                Quartet q1 = new Quartet(i,j,k,l,dm);
                alQuartets.add(q1);
                
                Quartet q2 = new Quartet(i,k,j,l,dm);
                alQuartets.add(q2);
                Quartet q3 = new Quartet(i,l,j,k,dm);
                alQuartets.add(q3);
                wmin = min(q1.weight,q2.weight,q3.weight);
                wmax = max(q1.weight,q2.weight,q3.weight);
                worst += wmax;
                best += wmin;
              }
            }
          }
        }
        worst_cost = new Double(worst);
        best_cost = new Double(best);
        return alQuartets;
    }
    public static Quartet [] generateFullQuartetList2(double [][] dm){
        double wmin, wmax, best, worst;
        ArrayList alQuartets = new ArrayList();
        worst = best = 0.0;
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                Quartet q1 = new Quartet(i,j,k,l,dm);
                alQuartets.add(q1);
                /*
                Quartet q2 = new Quartet(i,k,j,l,dm);
                alQuartets.add(q2);
                Quartet q3 = new Quartet(i,l,j,k,dm);
                alQuartets.add(q3);
                wmin = min(q1.weight,q2.weight,q3.weight);
                wmax = max(q1.weight,q2.weight,q3.weight);
                worst += wmax;
                best += wmin;
                */
              }
            }
          }
        }
        worst_cost = new Double(worst);
        best_cost = new Double(best);
        Quartet [] quartets = new Quartet[alQuartets.size()];
        for(int i=0;i<quartets.length;i++)
        {
        	quartets[i] = (Quartet)alQuartets.get(i);
        }
        return quartets;
    }
    public static void computeWorstAndBestCosts(double [][] dm){
        double wmin, wmax, best, worst;
        //ArrayList alQuartets = new ArrayList();
        worst = best = 0.0;
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++){
                Quartet q1 = new Quartet(i,j,k,l,dm);
                //alQuartets.add(q1);
                Quartet q2 = new Quartet(i,k,j,l,dm);
                //alQuartets.add(q2);
                Quartet q3 = new Quartet(i,l,j,k,dm);
                //alQuartets.add(q3);
                wmin = min(q1.weight,q2.weight,q3.weight);
                wmax = max(q1.weight,q2.weight,q3.weight);
                worst += wmax;
                best += wmin;
              }
            }
          }
        }
        worst_cost = new Double(worst);
        best_cost = new Double(best);
        //return alQuartets;
    }
    public static ArrayList generateBestQuartetList(double [][] dm){
        ArrayList alQuartets = new ArrayList();
        for (int i = 0; i < dm.length; i++){
          for (int j = i+1; j < dm.length; j++){
            for (int k = j+1; k < dm.length; k++){
              for (int l = k+1; l < dm.length; l++) {
                Quartet q1 = new Quartet(i,j,k,l,dm);
                //alQuartets.add(q1);
                Quartet q2 = new Quartet(i,k,j,l,dm);
                //alQuartets.add(q2);
                Quartet q3 = new Quartet(i,l,j,k,dm);
                //alQuartets.add(q3);
                if(q1.weight < q2.weight && q1.weight < q3.weight){
                	alQuartets.add(q1);
                }else if(q2.weight < q1.weight && q2.weight < q3.weight){
                	alQuartets.add(q2);
                }else{
                	alQuartets.add(q3);
                }
              }
            }
          }
        }
        return alQuartets;
    }
    static double min(double a, double b, double c){
        if(a <= b && a <= c)return a;
        else if(b <= a && b <= c)return b;
        else return c;
    }
    static double max(double a, double b, double c){
        if(a >= b && a >= c)return a;
        else if(b >= a && b >= c)return b;
        else return c;
    }
    public boolean equals(Object obj){
        Quartet q = (Quartet)obj;
        for(int i=0;i<4;i++){
            if(this.nodes[i]!=q.nodes[i])return false;
        }
        return true;
    }
    public boolean equals(Object obj, double [][] dm){
        Quartet q = (Quartet)obj;
        int count = 0;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(this.nodes[i] == q.nodes[j]){
                    count++;
                    break;
                }
            }
        }
        if(count < 4)return false;
        Quartet q2 = new Quartet(q.nodes[2],q.nodes[1],q.nodes[0],q.nodes[3],dm);
        Quartet q3 = new Quartet(q.nodes[3],q.nodes[1],q.nodes[2],q.nodes[0],dm);
        Quartet q4 = new Quartet(q.nodes[0],q.nodes[2],q.nodes[1],q.nodes[3],dm);
        Quartet q5 = new Quartet(q.nodes[0],q.nodes[3],q.nodes[2],q.nodes[1],dm);
        if(this.equals(q2)||this.equals(q3)||this.equals(q4)||this.equals(q5))return false;
        return true;
    }
}
